package lanQiaoBei.搜索与图论.最短路.floyd;
import java.io.*;
import java.math.*;
import java.util.*;

import javax.swing.InputMap;
/*floyd求多源最短路
*题目描述
定一个n个点m条边的有向图，图中可能存在重边和自环，边权可能为负数。

再给定k个询问，每个询问包含两个整数x和y，表示查询从点x到点y的最短距离，如果路径不存在，则输出“impossible”。

数据保证图中不存在负权回路。

输入格式
第一行包含三个整数n，m，k

接下来m行，每行包含三个整数x，y，z，表示点x和点y之间存在一条有向边，边长为z。

接下来k行，每行包含两个整数x，y，表示询问点x到点y的最短距离。

输出格式
共k行，每行输出一个整数，表示询问的结果，若询问两点间不存在路径，则输出“impossible”。

数据范围
1≤n≤200,
1≤k≤n2
1≤m≤20000,
图中涉及边长绝对值均不超过10000。

样例
输入样例：
3 3 2
1 2 1
2 3 2
1 3 1
2 1
1 3
输出样例：
impossible
1
* */
public class P1 {
       static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
       final static int N=210;
       static int d[][]=new int[N][N],n,m,q;
        
       static void floyd(){
    	      for(int k=1;k<=n;k++)
    	    	  for(int i=1;i<=n;i++)
    	    		  for(int j=1;j<=n;j++)
    	    			  d[i][j]=Math.min(d[i][j],d[i][k]+d[k][j]);
       }
       public static void main(String[] ss) throws IOException {	   
		      ss=br.readLine().split(" ");
		      n=Integer.parseInt(ss[0]);m=Integer.parseInt(ss[1]);q=Integer.parseInt(ss[2]);
		      for(int i=1;i<=n;i++){
		    	  Arrays.fill(d[i],0x3f3f3f3f);
		    	  //自己到自己必须初始化为零
		    	  d[i][i]=0;
		      }
		      while(m-->0){
		    	    ss=br.readLine().split(" ");
		    	    int a=Integer.parseInt(ss[0]),b=Integer.parseInt(ss[1]),c=Integer.parseInt(ss[2]);
		    	    d[a][b]=Math.min(d[a][b],c);
		      }
		      floyd();
		      while(q-->0){
		    	   ss=br.readLine().split(" ");
		    	   int a=Integer.parseInt(ss[0]),b=Integer.parseInt(ss[1]);
		    	   if(d[a][b]>0x3f3f3f3f/2)System.out.println("impossible");
		    	   else System.out.println(d[a][b]);
		      }
	   }
}
